﻿#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
using namespace std;

////////////////leetcode704.⼆分查找
class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else  return mid;
        }
        return -1;
    }
};
////////Leetcode34.在排序数组中查找元素的第⼀个和最后⼀个位置
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target)
//    {
//        vector<int>ret;
//        int size = nums.size() - 1;
//        int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) left = mid + 1;
//            else if (nums[mid] > target) right = mid - 1;
//            else
//            {
//                int start = mid, finish = mid;
//                while (start > 0 && nums[start - 1] == target) start--;
//                while (finish < size && nums[finish + 1] == target) finish++;
//                ret.push_back(start);
//                ret.push_back(finish);
//                return ret;
//            }
//        }
//        vector<int>fal{-1, -1};
//        return fal;
//    }   
//};

/////////////////////////优化版本；
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target)
//    {
//        if (nums.size() == 0)return { -1,-1 };
//        int begin = 0;
//        int left = 0, right = nums.size() - 1;
//        //寻找左端点;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] >= target) right = mid;
//            else left = mid + 1;
//        }
//        if (nums[left] == target) begin = left;
//        else return{ -1,-1 };
//        //寻找右端点;
//        right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] > target) right = mid - 1;
//            else left = mid;
//        }
//        return { begin,right };
//    }
//};
/////////35.搜索插⼊位置
//class Solution
//{
//public:
//    int searchInsert(vector<int>& nums, int target)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) left = mid + 1;
//            else right = mid;
//        }
//        if (nums[left] < target) return right + 1;
//        return right;
//    }
//};


///////////////69.x的平⽅根
//
//class Solution {
//public:
//    int mySqrt(int x)
//    {
//        if (x < 1) return 0;
//        int left = 1, right = x;
//        while (left < right)
//        {
//            long long int mid = left + (right - left + 1) / 2;
//            if (mid * mid <= x) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};

//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr)
//    {
//        int left = 0, right = arr.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid] > arr[mid - 1]) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};
// 
// 
// 
// 
//寻找峰值
//class Solution {
//public:
//    int findPeakElement(vector<int>& nums)
//    {
//        if (nums.size() == 1) return 0;
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if ((mid < nums.size() - 1) && nums[mid] < nums[mid + 1]) left = mid;
//            else if (mid > 0 && nums[mid] < nums[mid - 1]) right = mid - 1;
//            else return mid;
//        }
//        return left;
//    }
//};
//0~n - 1中缺失的数字
//class Solution {
//public:
//    int takeAttendance(vector<int>& records)
//    {
//        int left = 0, right = records.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (records[mid] == mid) left = mid + 1;
//            else right = mid;
//        }
//        return left == records[left] ? left + 1 : left;
//    }
//};
//int main()
//{
//    vector<int> nums{2, 1};
//    cout << findPeakElement(nums) << endl;;
//    return 0;
//}


//744. 寻找比目标字母大的最小字母
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target)
    {
        int left = 0, right = letters.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) left = mid + 1;
            else right = mid;
        }
        if (letters[left] > target) return letters[left];
        return letters[0];
    }
};